package 强化训练;

import java.util.ArrayList;
import java.util.Scanner;

public class day24迷宫问题 {
    static class Node {
        int x;
        int y;
        public Node(int x,int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] arr = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }
            ArrayList<Node> minPath = new ArrayList<>();
            ArrayList<Node> path = new ArrayList<>();

            int[][] pos = new int[m][n];

            minPathLen(arr,pos,0,0,path,minPath);

            for (Node node : minPath) {
                System.out.println("(" + node.x + "," + node.y + ")");
            }


        }
    }

    /**
     * 迷宫问题
     * @param arr 原来迷宫
     * @param pos 当前走过的路
     * @param x 当前位置
     * @param y 当前位置
     * @param path 走到出口的路径
     * @param minPath 最小路劲
     */
    public static void minPathLen(int[][] arr, int[][] pos, int x, int y, ArrayList<Node> path,ArrayList<Node> minPath){
        //终止条件
        //越界或者已经走过，或者存在障碍
        if (x < 0 || x > arr.length ||  y < 0 || y > arr[0].length || pos[x][y] == 1 || arr[x][y] == 1){
            return;
        }
        //否则当前位置为xy，将当前位置pos[x][y] = arr[x][y]，表示当前位置已经来过
        pos[x][y] = 1;
        path.add(new Node(x,y));
        //然后如果走到了出口，比较当前位置的路径和最小路径
        if (x == arr.length-1 && y == arr[0].length-1){
            if (minPath.isEmpty() || path.size() < minPath.size()){
                minPath.clear();
                for (Node node : path) {
                    minPath.add(node);
                }
            }
        }
        //向四个方向开始探索r
        minPathLen(arr,pos,x+1,y,path,minPath);
        minPathLen(arr,pos,x-1,y,path,minPath);
        minPathLen(arr,pos,x,y+1,path,minPath);
        minPathLen(arr,pos,x,y-1,path,minPath);

        //最终遍历结束，回退将当前出发点置为0，开始尝试其他路径，并将path删除，开始虚招其他路径
        pos[x][y] = 0;
        path.remove(path.size()-1);
    }
}
